package com.goudan.practice.other;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 计算器的实现
 * 实现一个计算器，只有加减法，没有括号，输入是一个字符串如1+2+3
 * 解题：表达式转化为后缀表达式（逆波兰表达式）
 */
public class Calculator {

    public static void main(String[] args) {
        String str = "10+2+3*5";
        // 表达式转换为操作数和操作符的中缀表达式数组
        String[] strArr = changeStrArr(str);
        // 中缀表达式转化为后缀表达式
        List<String> polandList = polandNotation(strArr);
        System.out.println(polandList);
        // 后缀表达式计算
        System.out.println(calculate(polandList));
    }

    /**
     * 字符串转成中缀的数组
     * 只有加减乘除，没有扩号
     */
    private static String[] changeStrArr(String str) {
        StringBuilder stringBuilder = new StringBuilder();
        for (char c : str.toCharArray()) {
            if ("+-*/".contains(String.valueOf(c))) {
                stringBuilder.append(";");
                stringBuilder.append(c);
                stringBuilder.append(";");
            } else {
                stringBuilder.append(c);
            }
        }
        return stringBuilder.toString().split(";");
    }

    /**
     * 中缀表达式转化为后缀表达式
     * 1.初始化两个栈，运算符栈s1和储存中间结果的栈s2
     * 2.从左到右扫描中缀表达式
     * 3.遇到操作数，入栈s2
     * 4.遇到运算符，比较其与s1栈顶运算符的优先级：
     * (1).如果s1为空，或者栈顶运算符为左括号"(",直接将运算符入栈；
     * (2).否则，若优先级比栈顶运算符高，也将运算符入栈s1;
     * (3).否则，将s1栈顶运算符弹出入栈s2中，再次转到(4-1) 与s1中新的栈顶运算符比较；
     * <p>
     * 本方法只考虑到加减乘除操作，不考虑扩号
     */
    private static List<String> polandNotation(String[] str) {
        List<String> s2 = new ArrayList<>();
        Stack<String> s1 = new Stack<>();
        for (String itm : str) {
            // 遇到操作数，直接入栈s2
            if (itm.matches("\\d+")) {
                s2.add(itm);
            } else {
                // 如果栈不为空，并且栈顶优先级比我目前运算符优先级高，就把栈顶运算符如s2，然后吧当前运算符如s1
                while (!s1.isEmpty() && Operation.getValue(s1.peek()) >= Operation.getValue(itm)) {
                    s2.add(s1.pop());
                }
                s1.push(itm);
            }
        }
        while (!s1.isEmpty()) {
            s2.add(s1.pop());
        }
        return s2;
    }

    /**
     * 运算符比较
     */
    private static class Operation {
        private static int ADD = 1;
        private static int SUB = 1;
        private static int MUL = 2;
        private static int DIV = 2;

        public static int getValue(String operation) {
            int result = 0;
            switch (operation) {
                case "+":
                    result = ADD;
                    break;
                case "-":
                    result = SUB;
                    break;
                case "*":
                    result = MUL;
                    break;
                case "/":
                    result = DIV;
                    break;
                default:
                    break;
            }
            return result;
        }

    }

    /**
     * 逆波兰表达式计算
     * 1.定义一个栈，匹配到非运算符就入栈
     * 2.遇到运算符就把栈顶两个数字出栈，用后出栈的数和先出栈的数做运算，把运算结果再入栈
     * 3.直到最后，栈顶结果即为计算结果
     */
    private static int calculate(List<String> polandList) {
        Stack<String> stack = new Stack<>();
        for (String itm : polandList) {
            // 匹配的是多位数
            if (itm.matches("\\d+")) {
                stack.push(itm);
            } else {
                // 弹出两个数，并运算，再入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if (itm.equals("+")) {
                    res = num1 + num2;
                } else if (itm.equals("-")) {
                    res = num1 - num2;
                } else if (itm.equals("*")) {
                    res = num1 * num2;
                } else if (itm.equals("/")) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符有误");
                }
                stack.push(String.valueOf(res));
            }
        }
        return Integer.parseInt(stack.pop());
    }

}
